package 力扣_链表.面试常考;

/**
 * @author zx
 * @create 2022-08-23 11:47
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/
 */
public class K个一组翻转链表_25 {
    /**
     * 面试写法(自己的总结：prev - next - start - end)
     */
    public ListNode reverseKGroup2(ListNode head, int k) {
        ListNode dummy = new ListNode(501);
        ListNode prev = dummy;
        ListNode end = head;
        dummy.next = head;
        while(end != null){
            for(int i = 0;i < k - 1 && end != null;i++){
                end = end.next;
            }
            if(end == null) break;
            ListNode next = end.next;
            end.next = null;
            ListNode start = prev.next;
            prev.next = reverse(start);
            start.next = next;
            prev = start;
            end = next;
        }
        return dummy.next;
    }
    /**
     * @return 这个题看那个题解的解答更容易理解
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //初始化pre和end都指向dummy
        ListNode pre = dummyHead;//每次要翻转的链表的头结点的上一个节点
        ListNode end = dummyHead;//每次要翻转的链表的尾节点
        while (end.next != null) {//细节3：
            //细节1：找到翻转链表的结尾,每次循环要判断end是否为空,如果为空,接下来不需要翻转
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            //细节2：如果end == null, 即需要翻转的链表的节点数小于k, 不执行翻转
            if (end == null) {
                break;
            }
            //先记录下end.next,方便后面链接链表
            ListNode next = end.next;
            //然后断开链表
            end.next = null;
            //记录下要翻转链表的头节点
            ListNode start = pre.next;
            //翻转链表,pre.next指向翻转后的链表; 1->2 变成 dummy->2->1
            pre.next = reverse(start);
            //翻转后头节点变到最后; 通过.next把断开的链表重新链接。
            start.next = next;
            //将pre换成下次要翻转的链表的头结点的上一个节点; 即start(类比dummyHead)
            pre = start;
            //翻转结束,将end置为下次要翻转的链表的头结点的上一个节点; 即start(类比dummyHead)
            end = start;
        }
        return dummyHead.next;
    }
    private ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}
